import java.util.*;
public class Test {
    /*
    题目 1 ：多数元素
     */
    //给定一个大小为 n 的数组 nums ，返回其中的多数元素。
    // 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    //自己的思路:使用哈希表，但是空间复杂度为 O(N)
    //空间复杂度：O(n)。哈希表最多包含 n - [n / 2] 个键值对
    public int majorityElement1(int[] nums) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int x : nums){
            if(map.get(x) == null){
                map.put(x,1);
            }else{
                int val = map.get(x);
                map.put(x,val + 1);
            }
        }
        for(int x : map.keySet()){
            if(map.get(x) > n / 2){
                return x;
            }
        }
        return -1;
    }
    //改进：可以在遍历数组的时候，维护最大值！
    //然而并没有快很多！
    public int majorityElement2(int[] nums) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        int key = 0;
        int value = 0;
        for(int x : nums){
            if(map.get(x) == null){
                map.put(x,1);
                if( 1 > value){
                    value = 1;
                    key = x;
                }
            }else{
                int val = map.get(x);
                map.put(x,val + 1);
                if(val + 1 > value){
                    value = val + 1;
                    key = x;
                }
            }
        }
        return key;
    }
    //方法二：先将数组进行排序，那么 n / 2 的位置，是众数的位置
    //写个快排！
    //使用三数取中法，速度才快点
    public int majorityElement3(int[] nums) {
        quicksort(nums);
        return nums[nums.length / 2];
    }
    private void quicksort(int[] nums){
        quick(nums , 0 , nums.length - 1);
    }
    private void quick(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int mid = (left + right)/2;
        int index = midTree(left,right,mid);
        swap(nums,index,left);
        int pivot = partition(nums,left,right);
        quick(nums, left, pivot - 1);
        quick(nums, pivot + 1, right);
    }
    private int partition(int[] nums, int left, int right){
        int temp = nums[left];
        while(left < right){
            while(left < right && nums[right] >= temp){
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= temp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }
    private int midTree(int A, int B, int C){
        if(A >= B){
            if(C >= A){
                return A;
            }else if(C <= B){
                return B;
            }else{
                return C;
            }
        }else{
            if(C >= B){
                return B;
            }else if(C <= A){
                return A;
            }else{
                return C;
            }
        }
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
    题目 2 ：颜色分类
     */
    //给定一个包含红色、白色和蓝色、共n 个元素的数组nums
    // 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    //我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
   //计数排序最好了
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for(int x : nums){
            count[x]++;
        }
        int j = 0;
        for(int i = 0; i < 3; i++){
            while(count[i] > 0){
                nums[j] = i;
                count[i]--;
                j++;
            }
        }
    }

    //官方解法：双指针
    //整个数组分成 3 部分，0 、1 、2
    //p0 指向 0 那部分的后一个位置，而 p1 指向 1 那部分的后一个位置
    //当 p0 < p1 时，意味着交换 i 与 p0 位置的元素时，1 会被换到 i 的位置
    //此时再让 i 与 p1 的位置进行交换
    //双指针
    public void sortColors1(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1){
                swap(nums, i, p1);
                p1++;
            }else if(nums[i] == 0){
                swap(nums, i, p0);
                if(p0 < p1){
                    swap(nums, i, p1);
                }
                p1++;
                p0++;
            }
        }
    }

    /*
    题目 3 ：合并区间
     */
    //以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
    // 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

    public int[][] merge(int[][] intervals) {
        //先排序
        //匿名内部类的写法：
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] arr1, int[] arr2){
                return arr1[0] - arr2[0];
            }
        });
        int j = 0;
        for(int i = 1; i < intervals.length; i++){
            //相邻两个区间有交集！
            if(intervals[j][1] >= intervals[i][0]){
                intervals[j][1] = Math.max(intervals[j][1], intervals[i][1]);
            }else{
                j++;
                intervals[j] = intervals[i];
            }
        }
        return Arrays.copyOf(intervals, j+1);
    }

    /*
    题目 4 ：杨辉三角2
     */
    //从 第 0 行开始
    //输入行，返回该行的杨辉三角数字
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i <= rowIndex; i++){
            list.add(1);
            for(int j = i - 1; j >= 1; j--){
                list.set(j, list.get(j) + list.get(j - 1));
            }
        }
        return list;
    }

    /*
    复习旧题目
     */
    //题目 1 ：删除有序数组中的重复数字
    //给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次
    // 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
    //自己的思路：交换
    public int removeDuplicates(int[] nums) {
        int end = 0;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[end]){
                end++;
                swap(nums, end, i);
            }
        }
        return end + 1;
    }

    /*
    题目 2 ：消失的数字
     */
    // 数组中本应包含 0 ~ n 的所有数字，但缺少某个数字，找到那个数字
    //方法一：等差数列求和
    public int missingNumber(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        int n = nums.length;
        return n * (n + 1) / 2 - sum;
    }

    //方法二：异或运算
    public int missingNumber1(int[] nums) {
        int ret = 0;
        for(int i = 0; i < nums.length; i++){
            ret ^= nums[i];
        }
        for(int i = 1; i <= nums.length; i++){
            ret ^= i;
        }
        return ret;
    }



















}
